package week7.util;
import java.util.*;

/**
 * 
 * Practicumopgave Programmeren 1
 * @author Rick Clement en Adriaan Dekker
 * @version $Revision: 1.3 $
 */
public abstract class SortedList<Elem> implements SortedSet<Elem> {
    // ------------------ Instantievariabelen ----------------
	protected List<Elem> list = new ArrayList<Elem>();
   
    // ------------------ Aanvragen --------------------------

    /**
     * Levert de lijst op.
     */
	protected List<Elem> getList() {
		return list;
	}
   
    // ------------------ Commando's --------------------------

	public boolean contains(Elem elem) {
		return list.contains(elem);
	}
	
	public int size() {
		return list.size();
	}
	
	/**
	 * Zoekt de index van het gegeven element.
	 */
	
	protected int itemIndex(Elem elem) {
		int onder = 0;
		int boven = this.size() - 1;
		// @invariant: elem groter dan this.get(0 .. onder-1) en
		// elem kleiner of gelijk this.get(boven .. size()-1)
		while (onder <= boven) {
			int midden = (onder + boven) / 2;
			if (lessThan(list.get(midden), elem)) 
				onder = midden+1;
			else 
				boven = midden-1;
		}
		return onder;
	}

	public boolean add(Elem elem) {
		if(!list.contains(elem)){
			int index = itemIndex(elem);
			list.add(index, elem);
			return true;
		} else return false;
	}

	public Elem get(int index) {
		return list.get(index);
	}

	public boolean remove(Elem elem) {
		boolean result = list.contains(elem);
		if (result) {
			int index = itemIndex(elem);
			list.remove(index);
		}
		return result;
	}

	public abstract boolean lessThan(Elem e1, Elem e2);
}
